package main

import "fmt"

func main() {
	fmt.Println(numDecodings("226"))
}

func numDecodings(s string) int {
	if s == "0" {
		return 0
	}
	chars := []rune(s)
	return decode(chars, len(chars)-1)
}

func decode(chars []rune, index int) int {
	if index <= 0 {
		return 1
	}

	count := 0

	curr := chars[index]
	prev := chars[index-1]

	if curr > '0' {
		count = decode(chars, index-1)
	}

	if prev == '1' || (prev == '2' && curr <= '6') {
		count += decode(chars, index-2)
	}

	return count
}
